package hwThree1;

import java.util.ArrayList;

// 作业 3.1.2
public class ArrayST<Key, Value> {
    private Key[] keys;       // 存储键的数组
    private Value[] values;   // 存储值的数组
    private int n;            // 符号表中键值对的数量

    // 构造函数：初始化符号表
    public ArrayST() {
        keys = (Key[]) new Object[2];       // 初始容量为 2
        values = (Value[]) new Object[2];
        n = 0;
    }

    // 判断符号表是否为空
    public boolean isEmpty() {
        return n == 0;
    }

    // 返回符号表中键值对的数量
    public int size() {
        return n;
    }

    // 检查符号表中是否包含指定键
    public boolean contains(Key key) {
        return get(key) != null;
    }

    // 获取指定键的值
    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        for (int i = 0; i < n; i++) {
            if (keys[i].equals(key)) {
                return values[i];
            }
        }
        return null; // 如果键不存在，返回 null
    }

    // 插入或更新键值对
    public void put(Key key, Value val) {
        if (key == null) throw new IllegalArgumentException("first argument to put() is null");
        if (val == null) { // 如果值为 null，则删除该键
            delete(key);
            return;
        }

        // 检查是否键已存在，存在则更新值
        for (int i = 0; i < n; i++) {
            if (keys[i].equals(key)) {
                values[i] = val; // 更新值
                return;
            }
        }

        // 如果符号表已满，则扩容
        if (n == keys.length) resize(2 * keys.length);

        // 插入新键值对
        keys[n] = key;
        values[n] = val;
        n++;
    }

    // 删除指定键及其对应的值
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to delete() is null");

        for (int i = 0; i < n; i++) {
            if (keys[i].equals(key)) {
                // 用最后一个元素替换被删除的键值对
                keys[i] = keys[n - 1];
                values[i] = values[n - 1];
                keys[n - 1] = null;
                values[n - 1] = null;
                n--;

                // 如果需要，缩小数组大小
                if (n > 0 && n == keys.length / 4) resize(keys.length / 2);
                return;
            }
        }
    }

    // 返回符号表中的所有键
    public Iterable<Key> keys() {
        ArrayList<Key> keyList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            keyList.add(keys[i]);
        }
        return keyList;
    }

    // 调整数组大小
    private void resize(int capacity) {
        Key[] tempKeys = (Key[]) new Object[capacity];
        Value[] tempValues = (Value[]) new Object[capacity];
        for (int i = 0; i < n; i++) {
            tempKeys[i] = keys[i];
            tempValues[i] = values[i];
        }
        keys = tempKeys;
        values = tempValues;
    }

    // 测试客户端
    public static void main(String[] args) {
        ArrayST<String, Integer> st = new ArrayST<>();
        st.put("A", 1);
        st.put("B", 2);
        st.put("C", 3);
        st.put("A", 4); // 更新 "A" 的值

        System.out.println("键值对：");
        for (String key : st.keys()) {
            System.out.println(key + " -> " + st.get(key));
        }

        st.delete("B"); // 删除 "B"
        System.out.println("删除 'B' 后的键值对：");
        for (String key : st.keys()) {
            System.out.println(key + " -> " + st.get(key));
        }
    }
}